/*
547.省份数量 https://leetcode.cn/problems/number-of-provinces/
2024/10/12 中等
题目的要求是计算给定城市连接矩阵中省份的数量。我的思路是通过遍历每个城市，若未被访问就进行深度优先搜索，把相连的城市都标记为已访问，每一轮这样的操作就代表一个省份。
*/
class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int provinces = 0;

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++;
            }
        }

        return provinces;
    }

private:
    void dfs(vector<vector<int>>& isConnected, vector<bool>& visited, int city) {
        visited[city] = true;
        for (int i = 0; i < isConnected.size(); ++i) {
            if (isConnected[city][i] == 1 &&!visited[i]) {
                dfs(isConnected, visited, i);
            }
        }
    }
};